
// 15.三数之和
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        // 枚举第一个位置
        int n = nums.size();
        sort(nums.begin() , nums.end());
        vector<vector<int>> ret;
        for(int i = 0 ; i < n - 2; i++)
        {
            if(i > 0 &&  nums[i] == nums[i - 1]) continue;
            if(nums[i] + nums[i + 1] + nums[i + 2] > 0 ) break; 
            if(nums[i] + nums[n - 2] + nums[n - 1] < 0 ) continue;

            int left = i + 1 , right = n -1;
            while(left < right)
            {
                if(nums[left] + nums[i] + nums[right] < 0) left++;
                else if(nums[left] + nums[i] + nums[right] > 0) right--;
                else 
                {
                    ret.push_back({nums[i] , nums[left++] , nums[right--]});
                    while(left < right && nums[left] == nums[left - 1]) left++;
                    while(left < right && nums[right] == nums[right + 1]) right--;
                }
            } 
        }            
        return ret;
    }
};